package com.gxc.array;

import java.util.*;

/**
 * 2742. 给墙壁刷油漆
 * 给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time ，分别表示给 n 堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠：
 *
 * 一位需要 付费 的油漆匠，刷第 i 堵墙需要花费 time[i] 单位的时间，开销为 cost[i] 单位的钱。
 * 一位 免费 的油漆匠，刷 任意 一堵墙的时间为 1 单位，开销为 0 。但是必须在付费油漆匠 工作 时，免费油漆匠才会工作。
 * 请你返回刷完 n 堵墙最少开销为多少。
 */
public class PaintWalls {

    public static void main(String[] args) {
        /*int[] cost = {1,2,3,2};
        int[] time = {1,2,3,2};
        System.out.println(handle(cost, time));
        System.out.println(handle(new int[]{2,3,4,2}, new int[]{1,1,1,1}));
        System.out.println(handle(new int[]{2,3,4,2}, new int[]{3,1,1,1}));
        System.out.println(handle(new int[]{8,7,5,15}, new int[]{1,1,2,1}));
        System.out.println(handle(new int[]{7, 9 ,10}, new int[]{2, 3, 1}));
        System.out.println(handle(new int[]{7, 9 ,10, 10}, new int[]{2, 3, 1, 1}));
        System.out.println(handle(new int[]{26,53,10,24,25,20,63,51}, new int[]{1,1,1,1,2,2,2,1}));
        System.out.println(handle(new int[]{49,35,32,20,30,12,42}, new int[]{1,1,2,2,1,1,2}));*/

        System.out.println(handle(new int[]{76,25,96,46,85,19,29,88,2,5}, new int[]{1,2,1,3,1,3,3,3,2,1}));

    }

    //贪心
    private static int handle(int[] cost, int[] time) {
        if (cost.length == 1) return cost[0];

        List<Cost> list = new LinkedList<>();
        for (int i = 0; i < cost.length; i++) {
            list.add(new Cost(cost[i], time[i]));
        }
        list.sort((o1, o2) -> {
            if (o1.cost == o2.cost) {
                return o2.time - o1.time;
            } else {
                return o1.cost - o2.cost;
            }
        });

        //print(list);
        int left = 0;
        int right = list.size()-1;

        int sum = 0;
        //任务总量
        int total = cost.length;
        while (left<=right) {
            int l = left;
            int r = right;
            while (l<=r){
                if (total>2 && list.get(l).time * 2 > total) {
                    sum += list.get(l).cost;
                    return sum;
                }
                l++;
            }
            sum += list.get(left).cost;
            int times = list.get(left).time;
            while (times>0){
                times--;
                right--;
                total--;
            }
            left++;
            total--;
        }

        return sum;
    }

    public static class Cost {
        int cost;
        int time;

        public Cost(int cost, int time) {
            this.cost = cost;
            this.time = time;
        }
    }

    private static void print(List<Cost> list) {
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i).cost + "," + list.get(i).time);
        }
    }
}
